package job.algorithm.sort;

import java.util.Arrays;

public class QuickSort {

	public static int partition(int[] arr, int begin, int end) {
		int small = begin - 1;
		for(int idx = begin; idx < end; idx ++) {
			if (arr[idx] < arr[end]) {
				++small;
				if(small != idx) {
					int tmp = arr[small];
					arr[small] = arr[idx];
					arr[idx] = tmp;
				}
			}
		}
		++small;
		int tmp = arr[small];
		arr[small] = arr[end];
		arr[end] = tmp;
		return small;
	}
	public static void quicksort(int[] arr, int begin, int end) {
		
		int idx = partition(arr, begin, end);
 
		if (idx > begin) {
			quicksort(arr, begin, idx-1);
		}
		if (idx < end) {
			quicksort(arr, idx+1, end);
		}
	}
	public static void main(String[] args) {
		
	}
}
